package ClassicDataStructuresAndAlgorithms.ClassicLinkedListAlgorithms;

public class Solution206 {
    public ListNode reverseList(ListNode head) {

        //我们用递归的思想来做一下这道题
        //定义reverseList函数：将输入的以head为头节点的单链表反转，并且返回新的头节点

        //写一下basecase
        if (head == null || head.next == null){
            return head;
        }

        ListNode last = reverseList(head.next);
        //我们思考递归函数，不能陷入到递归细节中去。
        //既然reverseList函数能帮我们把以head.next为首的单链表反转，那我管你这那的
        //想办法把当前的head连接到反转后的链表中去就完事了
        head.next.next = head;
        head.next = null;

        return last;
    }
}
